#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10,SQRTN = 700;
int a[N];
int ql[N],qr[N],qk[N],qi[N],qidx[N],qc;
int cp[N],cv[N],cbak[N],cc;
int bl[N];
bool cmp(int x,int y){
    return bl[ql[x]] < bl[ql[y]] || 
        bl[ql[x]] == bl[ql[y]] && bl[qr[x]] < bl[qr[y]] || 
        bl[ql[x]] == bl[ql[y]] && bl[qr[x]] == bl[qr[y]] && qi[x] < qi[y];
}
int tong[N];
int ctong[N];
random_device seed;
mt19937 mt(seed());
bitset<N> cm;
int cval[N];
void add(int x){
    ctong[tong[x]]--;
    if(ctong[tong[x]] == 0){
        cm[tong[x]] = 0;
    }
    tong[x]++;
    ctong[tong[x]]++;
    if(ctong[tong[x]] == 1){
        cm[tong[x]] = 1;    
    }
}
void remove(int x){
    ctong[tong[x]]--;
    if(ctong[tong[x]] == 0){
        cm[tong[x]] = 0;
    }
    tong[x]--;
    ctong[tong[x]]++;
    if(ctong[tong[x]] == 1){
        cm[tong[x]] = 1;    
    }
}
int ans[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    int ma = 0;
    for(int i = 1;i<=n;i++){
        cin>>a[i];
        ma = max(ma,a[i]);
    }
    for(int i = 1;i<=n;i++){
        cval[i] = mt();
    }
    for(int i = 1;i <= m;i++){
        int op;
        cin>>op;
        if(op == 1){
            int now = ++qc;
            cin>>ql[now]>>qr[now]>>qk[now];
            qi[now] = cc;
            qidx[now] = now;
        }else{
            int now = ++cc;
            cin>>cp[now]>>cv[now];
        }
    }
    int block = pow(n,2.0/3);
    int tot = n / block + (n % block != 0);
    for(int i = 1;i<=tot;i++)
    {
        int lp = (i - 1)*block + 1,rp = min(i * block,n);
        for(int j = lp;j <= rp;j++){
            bl[j] = i;
        }
    }
    sort(qidx + 1,qidx + 1 + qc,cmp);
    int cl = 1,cr = 0,ct = 0;
    for(int p = 1;p <= qc;p++){
        int l = ql[qidx[p]],r = qr[qidx[p]],t = qi[qidx[p]],i = qidx[p];
        while(cr < r){
            cr++;
            add(a[cr]);
        }
        while(cl > l){
            cl--;
            add(a[cl]);
        }
        while(cr > r){
            remove(a[cr]);
            cr--;
        }
        while(cl < l){
            remove(a[cl]);
            cl++;
        }
        while(ct < t){
            ct++;
            cbak[ct] = a[cp[ct]];
            a[cp[ct]] = cv[ct];
            if(l <= cp[ct] && cp[ct] <= r){
                remove(cbak[ct]);
                add(cv[ct]);
            }
        }
        while(ct > t){
            a[cp[ct]] = cbak[ct];
            if(l <= cp[ct] && cp[ct] <= r){
                remove(cv[ct]);
                add(cbak[ct]);
            }            
            ct--;
        }
        vector<int> ecnt;
        for(int v = cm._Find_first();v != cm.size();v = cm._Find_next(v)){
            ecnt.push_back(v);
        }
        auto p1 = ecnt.begin(),p2 = ecnt.begin();
        int sum = ctong[*p2];
        while(sum < qk[i]){
            p2++;
            if(p2 == ecnt.end())break;
            sum += ctong[*p2];
        }
        if(p2 == ecnt.end()){
            ans[i] = -1;
            continue;
        }
        while(sum - ctong[*p1] >= qk[i]){
            sum -= ctong[*p1];
            p1++;
        }
        ans[i] = *p2 - *p1;
        p2++;
        while(p2 != ecnt.end()){
            sum += ctong[*p2];
            while(sum - ctong[*p1] >= qk[i]){
                sum -= ctong[*p1];
                p1++;
            }
            ans[i] = min(ans[i],*p2 - *p1);
            p2++;
        }
    }
    for(int i = 1;i<=qc;i++){
        cout<<ans[i]<<'\n';
    }
}